<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html>

<head>
<title>sparse-switch</title>
<link rel=stylesheet href="opcode.css">
</head>

<body>

<h1>sparse-switch</h1>

<h2>Purpose</h2>

<p>
Jump to a new instruction based on the value in the given register, using an
ordered table of value-offset pairs, or fall through to the next instruction if
there is no match.
</p>
<p>
Note: The address of the table is guaranteed to be even (that is, 4-byte
aligned). If the code size of the method is otherwise odd, then an extra code
unit is inserted between the main code and the table whose value is the same as
a nop.
</p>

<h2>Details</h2>

<table class="instruc">
<thead>
<tr>
  <th>Op &amp; Format</th>
  <th>Mnemonic / Syntax</th>
  <th>Arguments</th>
</tr>
</thead>
<tbody>
<tr>
  <td>2c 31t</td>
  <td>sparse-switch vAA, +BBBBBBBB <i>(with supplemental data as
    specified below in "<code>sparse-switch</code> Format")</i></td>
  <td><code>A:</code> register to test<br/>
    <code>B:</code> signed "branch" offset to table data (32 bits)</td>
</tr>
</tbody>
</table>

<h2>Constraints</h2>

<ul>
  <li>
    A must be a valid register index in the current stack frame.
  </li>
  <li>
    Let PC be the address of the packed-switch instruction in the code array of
    the current method. Then T = PC + B with the following properties:
    <ul>
      <li>
        T must be 4-byte-aligned.
      </li>
      <li>
        T must be in the same method.
      </li>
      <li>
        T must point to a sparse-switch data table.
      </li>
    </ul>
  </li>
</ul>

<h2>Behavior</h2>

<ul>
  <li>
    The value of vA is used as a lookup key inside the sparse table data.
  </li>
  <li>
    If there exists an I with 0 <= I < table.size such that table.keys[I] = vA,
    then the jump target is determined as follows:
    <ul>
      <li>
        PC' = PC + table.targets[I].
      </li>
      <li>
        Execution will resume at this address.
      </li>
    </ul>
  </li>
  <li>
    Otherwise execution continues at the instruction following the sparse-switch
    statement.
  </li>
</ul>

<h2>Exceptions</h2>

<p>
None.
</p>

<h2>Notes</h2>

<p>
The low-to-high ordering of the keys allows the VM to employ binary search for
the lookup, resulting in O(log table.size) comparisons.
</p>

</body>
</html>
